#define _CRT_SECURE_NO_WARNINGS 1
ListNode* serch_mid(ListNode* head) {
    ListNode* fast = head, * slow = head;
    while (fast && fast->next) {
        fast = fast->next->next;
        slow = slow->next;
    }
    return slow;
}
ListNode* reverse(ListNode* phead) {
    ListNode* prev = NULL;
    ListNode* cur = phead;
    while (cur) {
        ListNode* next = cur->next;
        cur->next = prev;
        prev = cur;
        cur = next;
    }
    return prev;
}
class PalindromeList {
public:
    bool chkPalindrome(ListNode* A) {
        ListNode* mid = serch_mid(A);
        ListNode* rmid = reverse(mid);
        while (rmid) {
            if (A->val != rmid->val) {
                return false;
            }
            A = A->next;
            rmid = rmid->next;
        }
        return true;
    }
};